/LMAR=50/TMAR=50/RMAR=4095/BMAR=1/PMAR=0/XLINE=0/FONT#0=NGR13/USETI=0000059*TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX*

␈β↓R␈↓ λ↑␈εαCS204←Autumn␈α1978
␈βαλ␈↓ ↓H␈ε∩Problem␈α1.␈εα␈αThe␈αcamel␈αof␈αKho␈α␈w␈↓ ¬3␈εα∂␈↓ ¬3␈εαa␈↓ ¬E␈εαrizm.␈↓ π%(warm␈α␈up␈αproblem,␈αdue␈αOctober␈α5)
␈βα?␈↓ βL␈∧α?βLα∩
␈βα@␈↓ β(␈ε⊗p
␈βαE␈↓ ↓H␈εαLet␈↓ α
␈ελ≡␈↓ α(␈εα=␈α
(1␈αλ+␈↓ βL␈εα5␈↓ βd␈εα)/2␈α
=␈α
1.61803␈α39887␈α49894␈α84820␈↓ λ␈εα.␈αε.␈αε.␈↓ λ6␈εαbe␈αthe␈α\golden␈αratio."
␈βαp␈↓ α␈εαA␈αlegendary␈α
camel␈αin␈α
the␈αancien␈α␈t␈αPersian␈α
valley␈αof␈αKho␈α␈w␈↓ 	⊃␈εα∂␈↓ 	⊃␈εαa␈↓ 	#␈εαrizm␈α
used␈αto␈αwalk
␈ββ≠␈↓ ↓H␈εαaround␈α
and␈α	around␈α
on␈α
a␈α
circular␈α
road␈α
that␈α
was␈α
exactly␈α
one␈α
parathanha␈α
in␈α	circum-
␈ββF␈↓ ↓H␈εαference.␈αEv␈α␈ery␈αtime␈α
this␈αcamel␈α
w␈α␈ould␈αtrav␈α␈el␈α
a␈αdistance␈α
of␈αprecisely␈↓ 	\␈ελ≡␈↓ 	z␈εαparathanh≤,
␈ββr␈↓ ↓H␈εαit␈αw␈α␈ould␈αdeposit␈αsome␈αbeautiful␈αdung␈αthat␈αshone␈αlik␈α␈e␈αgold.␈αThe␈αgolden␈αdung␈αwas,
␈β∧≥␈↓ ↓H␈εαof␈αcourse,␈αbewitched;␈αit␈αwas␈αcertain␈αdeath␈αto␈αan␈α␈y␈α␈one␈αwho␈αtouched␈αit␈αor␈αdisturbed
␈β∧H␈↓ ↓H␈εαit␈αin␈αan␈α␈y␈αway.␈αTh␈α␈us,␈αo␈α␈v␈α␈er␈αthe␈αy␈α␈ears␈αa␈αseries␈αof␈αsuch␈αdeposits␈αcon␈α␈tin␈α␈ued␈αto␈αbe␈αbuilt
␈β∧s␈↓ ↓H␈εαup␈αalong␈αthe␈αroad.
␈β¬≡␈↓ α␈εαEv␈α␈ery␈α␈one␈α∞who␈α∂passed␈α∞that␈α∞way␈α∞noticed␈α∞a␈α∂strange␈α∞thing←the␈α∞golden␈α∞camel-
␈β¬J␈↓ ↓H␈εαdung␈α∞seemed␈α∂to␈α∂be␈α∞almost␈α∂equally␈α∞spaced.␈α∀One␈α∂could␈α∂practically␈α∞use␈α∂the␈α∞heaps
␈β¬u␈↓ ↓H␈εαas␈α∂mileposts.␈α∀In␈α∂fact,␈α⊂at␈α∞the␈α∂time␈α∂when␈α∂there␈α∂w␈α␈ere␈↓ λε␈ελn␈↓ λ*␈εαdeposits␈α∂on␈α∂the␈α∂road,␈α∂the
␈βε ␈↓ ↓H␈εαfollo␈α␈wing␈α	condition␈α	was␈α
true␈α	(although␈α	only␈α
a␈α	few␈α	mathematicians␈α	knew␈α
it):␈α
There
␈βεK␈↓ ↓H␈εαwas␈αa␈αpoin␈α␈t␈↓ βλ␈ελx␈↓ β6␈εαon␈αthe␈αroad␈αsuch␈αthat␈αif␈αy␈α␈ou␈αstarted␈αat␈↓ λ#␈ελx␈↓ λQ␈εαy␈α␈ou␈αw␈α␈ould␈αpass␈αexactly
␈βεY␈↓ β_␈εn␈↓ λ4␈εn
␈βεv␈↓ ↓H␈εαone␈αgolden␈αdung␈αheap␈αduring␈αthe␈αtime␈αit␈αtook␈αto␈αtrav␈α␈el␈αone␈↓ λv␈ελn␈↓ 	␈εαth␈αof␈αa␈αparathanha.
␈βπ"␈↓ ↓H␈εαRepeating␈α∂this␈↓ β?␈ελn␈↓ βc␈εαtimes␈α∂un␈α␈til␈α∂returning␈α∂to␈↓ εn␈ελx␈↓ π⊃␈εα,␈α∂y␈α␈ou␈α∂w␈α␈ould␈α∂see␈α∂only␈α∂one␈α∂heap␈α∂per
␈βπ/␈↓ ε␈␈εn
␈βπM␈↓ ↓H␈εαsegmen␈α␈t␈α∞of␈α∂y␈α␈our␈α∂tour.␈α∀The␈α∞mathematicians␈α∂of␈α∂that␈α∞time␈α∂called␈α∞this␈α∂the␈α∂\␈↓ 
a␈ελn␈↓ 
v␈εα-fold
␈βπx␈↓ ↓H␈εαcy␈α␈clic␈αdung␈αdistribution␈αproperty."
␈βλ#␈↓ α␈εαThe␈αmagic␈αcamel␈αnev␈α␈er␈αleft␈αthe␈αroad,␈αand␈αit␈αcon␈α␈tin␈α␈ued␈αto␈αmak␈α␈e␈αits␈αenchan␈α␈ted
␈βλN␈↓ ↓H␈εαdeposits␈α∞for␈α∞man␈α␈y␈α∞y␈α␈ears.␈α∩Ev␈α␈ery␈α∞time␈↓ ε∨␈ελn␈↓ εB␈εαw␈α␈ould␈α∞increase␈α∞by␈α∞one,␈α∂the␈↓ 	|␈ελn␈↓ 
⊃␈εα-fold␈α∞cy␈α␈clic
␈βλz␈↓ ↓H␈εαdung␈α
distribution␈α∞property␈α∞remained␈α
valid.␈α⊃But␈α∞one␈α∞y␈α␈ear,␈α∞just␈α
as␈α∞a␈α∞new␈α
deposit
␈β	%␈↓ ↓H␈εαwas␈α	about␈α
to␈α	be␈α
made,␈α
a␈α	m␈α␈ysterious␈α
cloud␈α	appeared␈α
and␈α	en␈α␈v␈α␈eloped␈α	the␈α
poor␈α	beast;
␈β	P␈↓ ↓H␈εαand␈αwhen␈αthe␈αcloud␈αmo␈α␈v␈α␈ed␈αaway,␈αthe␈αcamel␈αwas␈αgone.␈αThe␈αspell␈αwas␈αbrok␈α␈en,␈αand
␈β	{␈↓ ↓H␈εαthe␈αgold␈αcould␈αno␈α␈w␈αbe␈αfreely␈αtak␈α␈en.
␈β
&␈↓ α␈εαOne␈α	of␈α	the␈αλmathematicians␈α	had␈α	an␈α␈ticipated␈α	this,␈α	since␈α	he␈α	knew␈αλthat␈α	the␈↓ 
a␈ελn␈↓ 
v␈εα-fold
␈β
R␈↓ ↓H␈εαcy␈α␈clic␈αdung␈αdistribution␈αproperty␈αw␈α␈ould␈αfail␈αat␈αthe␈αtime␈αof␈αthe␈αnext␈αdeposit.␈αThis
␈β
⎇␈↓ ↓H␈εαbrillian␈α␈t␈α
sorceror␈α∞had␈α
made␈α∞preparations␈α∞for␈α
the␈α∞fateful␈α
momen␈α␈t,␈α∞and␈α∞his␈α
agen␈α␈ts
␈β(␈↓ ↓H␈εαimmediately␈α
pounced␈α∞on␈α
the␈α
gold␈α∞when␈α
the␈α∞enchan␈α␈tmen␈α␈t␈α
was␈α∞lifted.␈α⊂He␈α
became
␈βS␈↓ ↓H␈εαthe␈α
richest␈α∞man␈α∞in␈α∞the␈α∞valley,␈α∞so␈α∞he␈α
gav␈α␈e␈α∞up␈α∞mathematics␈α∞and␈α∞was␈α
assassinated
␈β}␈↓ ↓H␈εαt␈α␈w␈α␈o␈αmon␈α␈ths␈αlater.
␈β*␈↓ α␈εαThe␈αproblem␈αis␈αto␈αdetermine␈↓ ¬Y␈ελx␈↓ ελ␈εαfor␈↓ ε@␈ελn␈↓ ε←␈εα=␈α
1,␈α2,␈↓ π]␈εα.␈αε.␈αε.␈↓ λ
␈εα;␈αand␈αto␈αdetermine␈αthe␈α|nal
␈β7␈↓ ¬j␈εn
␈βU␈↓ ↓H␈εαvalue␈αof␈↓ αR␈ελn␈↓ αs␈εαwhen␈αthe␈αcamel␈αvanished.
␈β∂.␈↓ ε:␈εα1
␈β⊃∂

␈β↓R␈↓ λ↑␈εαCS204←Autumn␈α1978
␈βαλ␈↓ ↓H␈ε∩Problem␈α2.␈εα␈αBit␈α|ddling␈αand␈αimage␈αprocessing.␈↓ 	4(due␈αOctober␈α19)
␈βαE␈↓ ↓H␈εαIn␈αthis␈αproblem␈αw␈α␈e␈α
will␈αbe␈αdealing␈αwith␈αpictures␈α
represen␈α␈ted␈αon␈αa␈αdiscrete␈αraster.
␈βαp␈↓ ↓H␈εαWe␈α∞hav␈α␈e␈α
an␈↓ β∀␈ελn␈↓ β3␈ε⊗α␈↓ βa␈ελn␈↓ ∧∧␈εαgrid␈α∞consisting␈α∞of␈α∞square␈α∞\pix␈α␈els,"␈α∞each␈α∞of␈α∞which␈α∞is␈α∞white␈α
or
␈ββ≠␈↓ ↓H␈εαblack.␈α∃Using␈α⊂0␈α∂to␈α∂represen␈α␈t␈α∂white␈α⊂and␈α∂1␈α∂to␈α∂represen␈α␈t␈α∂black,␈α⊃w␈α␈e␈α∂will␈α∂be␈α∂able␈α∂to
␈ββF␈↓ ↓H␈εαrepresen␈α␈t␈αλthe␈α	picture␈α	compactly␈α	with␈αλ36␈α	pix␈α␈els␈α	per␈α	w␈α␈ord␈αλ(on␈α	the␈α	AI␈α	Lab␈αλcomputer),
␈ββr␈↓ ↓H␈εαand␈α	the␈αλcomputer's␈α	Boolean␈α	operations␈α	will␈α	facilitate␈α	the␈α	manipulation␈α	of␈αλpictures.
␈β∧≥␈↓ ↓H␈εαThere␈αare␈αt␈α␈w␈α␈o␈α
parts␈αto␈αthis␈αproblem:␈α
|rst␈αto␈α
\clean␈αup"␈αa␈αpicture,␈α
and␈αsecond␈αto
␈β∧H␈↓ ↓H␈εαdo␈αedge-follo␈α␈wing␈αthat␈α
described␈αthe␈αboundaries␈α
of␈αthe␈α\objects"␈α
in␈αa␈αcleaned-up
␈β∧s␈↓ ↓H␈εαpicture.
␈β¬&␈↓ ↓H␈εαA.␈ε∂␈α
The␈α∞cleaning-up␈α
phase␈εα␈α∞is␈α∞in␈α␈tended␈α
to␈α∞change␈α
stray␈α∞black␈α∞pix␈α␈els␈α
to␈α∞white␈α
and
␈β¬I␈↓ λd␈ε_¬
␈β¬Q␈↓ ↓H␈εαvice␈α
v␈α␈ersa,␈α
as␈α
w␈α␈ell␈αas␈α
to␈α
remo␈α␈v␈α␈e␈α
sharp␈α
turns␈α
of␈αmore␈α
than␈α
9␈↓ λV␈εα0␈↓ λ}␈εαat␈α
the␈α
edges␈α
of␈α
black
␈β¬|␈↓ ↓H␈εαareas.
␈βε'␈↓ α␈εαFor␈α
purposes␈αof␈α
discussion,␈αa␈α
picture␈↓ εN␈ελP␈↓ εr␈εαwill␈α
be␈αregarded␈α
as␈α
the␈αset␈α
of␈α
all␈α
black
␈βεM␈↓ πx␈ε→␈
␈βεR␈↓ ↓H␈εαpix␈α␈els␈αin␈αsome␈αimage,␈α
and␈αthe␈αcomplemen␈α␈tary␈α
set␈↓ π↑␈ελP␈↓ λ!␈εαwill␈αbe␈αthe␈α
set␈αof␈αall␈αwhite
␈βεy␈↓ ¬&␈εC
␈βε}␈↓ ↓H␈εαpix␈α␈els.␈αWe␈α
de|ne␈α
the␈ε∂␈α
closure␈↓ ¬␈ελP␈↓ ¬H␈εαof␈↓ ¬p␈ελP␈↓ ε∪␈εαto␈α
be␈α
the␈αsmallest␈α
picture␈α
con␈α␈taining␈↓ 
U␈ελP␈↓ 
x␈εαsuch
␈βπ$␈↓ π8␈εC␈↓ πO␈ε→␈
␈βπ)␈↓ ↓H␈εαthat␈α
ev␈α␈ery␈α∞white␈α∞pix␈α␈el␈α∞(i.e.,␈α∞ev␈α␈ery␈α
elemen␈α␈t␈α∞of␈↓ π≡␈ελP␈↓ πl␈εα)␈α∞is␈α
part␈α∞of␈α∞a␈α∞3␈ε⊗␈α	α␈εα␈α	3␈α∞square␈α
of
␈βπO␈↓ 
Y␈εO
␈βπT␈↓ ↓H␈εαwhite␈αpix␈α␈els.␈α
A␈α
picture␈αis␈ε∂␈αclosed␈εα␈α
if␈αit␈αis␈α
equal␈αto␈α
its␈αclosure.␈α
The␈ε∂␈α
in␈α␈terior␈↓ 
?␈ελP␈↓ 
z␈εαof␈↓ %␈ελP
␈βπ␈␈↓ ↓H␈εαis␈αde|ned␈α
to␈α
be␈α
the␈α
largest␈αpicture␈α
con␈α␈tained␈α
in␈↓ πD␈ελP␈↓ πj␈εαsuch␈α
that␈α
ev␈α␈ery␈α
black␈α
pix␈α␈el␈αis
␈βλ*␈↓ ↓H␈εαpart␈α
of␈α
a␈α	3␈ε⊗␈αεα␈εα␈α¬3␈α
square␈α
of␈α
black␈α
pix␈α␈els.␈αA␈α
picture␈α
is␈ε∂␈α
open␈εα␈α
if␈α
it␈α
is␈α
equal␈α
to␈α
its␈α	in␈α␈terior.
␈βλV␈↓ α␈εαExamples:␈α∩(Imagine␈α	in|nitely␈α	man␈α␈y␈α	white␈α	pix␈α␈els␈α	surrounding␈α	these␈αλdiagrams)
␈β	⊗␈↓ β␈εα1␈α1␈α0␈α0␈α1␈α1␈↓ ε
␈εα1␈α1␈α1␈α1␈α1␈α1␈↓ 	%␈εα0␈α1␈α1␈α1␈α1␈α0
␈β	B␈↓ β␈εα1␈α1␈α0␈α0␈α1␈α0␈↓ ε
␈εα1␈α1␈α1␈α1␈α1␈α0␈↓ 	%␈εα0␈α1␈α1␈α1␈α1␈α0
␈β	d␈↓ ¬>␈εC␈↓ λ@␈εC␈↓ λX␈εO
␈β	i␈↓ α9␈ελP␈↓ α]␈εα=␈↓ ¬$␈ελP␈↓ ¬←␈εα=␈↓ λ&␈ελP␈↓ λw␈εα=
␈β	m␈↓ β␈εα0␈α1␈α1␈α1␈α1␈α0␈↓ ε
␈εα0␈α1␈α1␈α1␈α1␈α0␈↓ 	%␈εα0␈α1␈α1␈α1␈α1␈α0
␈β
_␈↓ β␈εα0␈α1␈α1␈α1␈α0␈α0␈↓ ε
␈εα0␈α1␈α1␈α1␈α0␈α0␈↓ 	%␈εα0␈α1␈α1␈α1␈α0␈α0
␈β
C␈↓ β␈εα0␈α0␈α1␈α0␈α0␈α0␈↓ ε
␈εα0␈α0␈α1␈α0␈α0␈α0␈↓ 	%␈εα0␈α0␈α0␈α0␈α0␈α0
␈β
{␈↓ 	≡␈εC␈↓ 	6␈εO
␈β␈↓ α␈εαThe␈α
|rst␈αsubproblem␈α
is␈α
to␈α
replace␈αa␈α
giv␈α␈en␈α
picture␈↓ λ)␈ελP␈↓ λP␈εαby␈↓ 	∧␈ελP␈↓ 	K␈εα,␈α
the␈α
in␈α␈terior␈αof
␈β'␈↓ λk␈εC␈↓ 	β␈εO
␈β,␈↓ ↓H␈εαits␈αclosure.␈αWe␈αwill␈αsay␈αthat␈αa␈αpicture␈αis␈ε∂␈αclean␈εα␈αif␈αit␈αequals␈↓ λR␈ελP␈↓ 	$␈εαfor␈αsome␈↓ 
5␈ελP␈↓ 
O␈εα.␈αWrite
␈βR␈↓ ∧3␈εC␈↓ ∧K␈εO
␈βW␈↓ ↓H␈εαa␈αprogram␈αthat␈α|nds␈↓ ∧~␈ελP␈↓ ∧`␈εα,␈αgiv␈α␈en␈αa␈α72␈ε⊗␈αλα␈εα␈αλ72␈αpicture␈↓ πu␈ελP␈↓ λ∂␈εα.
␈βα␈↓ α␈εαWhile␈α
solving␈αthis␈α
problem␈αy␈α␈ou␈α
may␈αwish␈αto␈α
dev␈α␈elop␈αa␈α
theory␈αalong␈α
the␈αfol-
␈β-␈↓ ↓H␈εαlo␈α␈wing␈αlines.␈αLet␈αus␈αwrite
␈βn␈↓ ↓a␈ελx␈↓ ↓}␈ε⊗≡␈↓ α,␈ελy␈↓ βλ␈εαif␈↓ β*␈εαro␈α␈w␈↓ βc␈εα(␈↓ βo␈ελx␈↓ ∧α␈εα)␈ε⊗␈α
∀␈↓ ∧F␈εαro␈α␈w␈↓ ∧␈␈εα(␈↓ ¬␈ελy␈↓ ¬∨␈εα)␈ε⊗␈α
∀␈↓ ¬c␈εαro␈α␈w␈↓ ε≤␈εα(␈↓ ε(␈ελx␈↓ ε;␈εα)␈αλ+␈αλ2␈αand␈↓ π←␈εαcol␈↓ λ␈εα(␈↓ λ↔␈ελx␈↓ λ*␈εα)␈ε⊗␈α
∀␈↓ λn␈εαcol␈↓ 	~␈εα(␈↓ 	&␈ελy␈↓ 	:␈εα)␈ε⊗␈α
∀␈↓ 	}␈εαcol␈↓ 
*␈εα(␈↓ 
6␈ελx␈↓ 
I␈εα)␈αλ+␈αλ2;
␈β
→␈↓ ↓a␈ελx␈↓ ↓}␈ε⊗∨␈↓ α,␈ελy␈↓ βλ␈εαif␈↓ β*␈εαro␈α␈w␈↓ βc␈εα(␈↓ βo␈ελx␈↓ ∧α␈εα)␈ε⊗␈αλ␈␈εα␈αλ2␈ε⊗␈α
∀␈↓ ¬␈εαro␈α␈w␈↓ ¬E␈εα(␈↓ ¬Q␈ελy␈↓ ¬e␈εα)␈ε⊗␈α
∀␈↓ ε)␈εαro␈α␈w␈↓ εb␈εα(␈↓ εn␈ελx␈↓ π↓␈εα)␈αand␈↓ π←␈εαcol␈↓ λ␈εα(␈↓ λ↔␈ελx␈↓ λ*␈εα)␈ε⊗␈αλ␈␈εα␈αλ2␈ε⊗␈α
∀␈↓ 	4␈εαcol␈↓ 	`␈εα(␈↓ 	l␈ελy␈↓ 
␈εα)␈ε⊗␈α
∀␈↓ 
D␈εαcol␈↓ 
p␈εα(␈↓ 
|␈ελx␈↓ ∂␈εα).
␈β
Z␈↓ ↓H␈εαFurthermore␈αw␈α␈e␈αde|ne
␈β∞∩␈↓ ∧@␈ε→≡
␈β∞↔␈↓ ∧&␈ελP␈↓ ∧g␈εα=␈↓ ¬∃␈ε⊗f␈↓ ¬-␈ελx␈↓ ¬I␈ε⊗j␈↓ ¬]␈ελx␈↓ ¬z␈ε⊗≡␈↓ ε(␈ελy␈↓ εH␈εαfor␈αsome␈↓ πZ␈ελy␈↓ πz␈εαin␈↓ λ$␈ελP␈↓ λD␈ε⊗g␈↓ λV␈εα;
␈β∞=␈↓ ∧@␈ε→∨
␈β∞B␈↓ ∧&␈ελP␈↓ ∧g␈εα=␈↓ ¬∃␈ε⊗f␈↓ ¬-␈ελx␈↓ ¬I␈ε⊗j␈↓ ¬]␈ελx␈↓ ¬z␈ε⊗∨␈↓ ε(␈ελy␈↓ εH␈εαfor␈αsome␈↓ πZ␈ελy␈↓ πz␈εαin␈↓ λ$␈ελP␈↓ λD␈ε⊗g␈↓ λV␈εα.
␈β∂.␈↓ ε:␈εα2
␈β⊃∂

␈β↓R␈↓ ↓H␈εαIn␈αthese␈αterms,␈αpro␈α␈v␈α␈e␈αor␈αdispro␈α␈v␈α␈e␈αthe␈αfollo␈α␈wing␈αstatemen␈α␈ts:
␈βα¬␈↓ α↔␈ε→␈␈↓ α4␈εC␈↓ αL␈ε→␈␈↓ β:␈εO
␈βα
␈↓ ↓H␈εα(1)␈↓ ↓}␈ελP␈↓ αs␈εα=␈↓ β!␈ελP␈↓ βP␈εα.
␈βα1␈↓ α↔␈εO
␈βα6␈↓ ↓H␈εα(2)␈↓ ↓}␈ελP␈↓ α9␈εαis␈αthe␈αunion␈αof␈αall␈α3␈ε⊗␈αλα␈εα␈αλ3␈αsquare␈αblack␈αpictures␈αcon␈α␈tained␈αin␈↓ 	d␈ελP␈↓ 	⎇␈εα.
␈βαb␈↓ ↓H␈εα(3)␈↓ ↓}␈ελx␈↓ α~␈ε⊗≡␈↓ αH␈ελy␈↓ αi␈εαif␈αand␈αonly␈αif␈↓ ∧C␈ελy␈↓ ∧a␈ε⊗∨␈↓ ¬∂␈ελx␈↓ ¬!␈εα.
␈ββ	␈↓ α↔␈ε→≡
␈ββ∞␈↓ ↓H␈εα(4)␈↓ ↓}␈ελP␈↓ α@␈εαis␈αopen.
␈ββ5␈↓ α↔␈εO␈↓ α}␈ε→␈≡␈∨
␈ββ:␈↓ ↓H␈εα(5)␈↓ ↓}␈ελP␈↓ α7␈εα=␈↓ αe␈ελP␈↓ βr␈εα.
␈ββf␈↓ ↓H␈εα(6)␈α	If␈↓ α≥␈ελP␈↓ α@␈εαis␈α
a␈α	picture␈α
such␈α	that␈α
ev␈α␈ery␈α	black␈α
pix␈α␈el␈α
is␈α	included␈α
in␈α	a␈α
set␈α	of␈α
3␈α	consecutiv␈α␈e
␈β∧⊃␈↓ α⊂␈εαblack␈αpix␈α␈els␈αin␈αthe␈αsame␈αro␈α␈w␈αand␈αin␈αa␈αset␈αof␈α3␈αconsecutiv␈α␈e␈αblack␈αpix␈α␈els␈αin␈αthe
␈β∧<␈↓ α⊂␈εαsame␈αcolumn,␈αthen␈↓ ∧D␈ελP␈↓ ∧i␈εαis␈αopen.
␈β∧h␈↓ ↓H␈εα(7)␈α
If␈↓ α$␈ελP␈↓ αK␈εαis␈α
a␈α
clean␈α
picture␈α
and␈α
if␈↓ ¬Q␈ελx␈↓ ¬d␈εα,␈↓ ¬{␈ελy␈↓ ε∂␈εα,␈↓ ε'␈ελz␈↓ εC␈εαare␈α
three␈α
consecutiv␈α␈e␈α
elemen␈α␈ts␈α
of␈α
a␈α
ro␈α␈w,
␈β¬∀␈↓ α⊂␈εαwhere␈↓ αu␈ελx␈↓ β∩␈ε⊗2␈↓ β8␈ελP␈↓ βQ␈εα,␈↓ βe␈ελy␈↓ ∧β␈ε⊗3␈↓ ∧)␈ελP␈↓ ∧C␈εα,␈α
and␈↓ ¬~␈ελz␈↓ ¬3␈ε⊗2␈↓ ¬Y␈ελP␈↓ ¬s␈εα,␈α
then␈α	the␈α	pix␈α␈els␈α
immediately␈α	abo␈α␈v␈α␈e␈α	and␈α	belo␈α␈w
␈β¬?␈↓ α⊂␈ελy␈↓ α0␈εαare␈αnot␈αin␈↓ βV␈ελP␈↓ βo␈εα.
␈β¬k␈↓ ↓H␈εα(8)␈αIf␈↓ α ␈ελP␈↓ αE␈εαis␈αa␈αclean␈αpicture␈αand␈αif␈↓ ¬A␈ελw␈↓ ¬\␈εα,␈↓ ¬q␈ελx␈↓ ε∧␈εα,␈↓ ε~␈ελy␈↓ ε.␈εα,␈↓ εC␈ελz␈↓ ε↑␈εαare␈αfour␈αconsecutiv␈α␈e␈αelemen␈α␈ts␈αof␈αa␈αro␈α␈w,
␈βε⊗␈↓ α⊂␈εαwhere␈↓ αx␈ελw␈↓ β∨␈ε⊗2␈↓ βF␈ελP␈↓ β`␈εα,␈↓ βw␈ελx␈↓ ∧∃␈ε⊗3␈↓ ∧<␈ελP␈↓ ∧V␈εα,␈↓ ∧m␈ελy␈↓ ¬
␈ε⊗3␈↓ ¬4␈ελP␈↓ ¬N␈εα,␈α
and␈↓ ε,␈ελz␈↓ εF␈ε⊗2␈↓ εm␈ελP␈↓ ππ␈εα,␈α
then␈α
the␈α
pix␈α␈els␈α
immediately␈αabo␈α␈v␈α␈e
␈βεA␈↓ α⊂␈εαand␈αbelo␈α␈w␈↓ β;␈ελx␈↓ βY␈εαand␈↓ ∧∨␈ελy␈↓ ∧@␈εαare␈αnot␈αin␈↓ ¬f␈ελP␈↓ ¬␈␈εα.
␈βεm␈↓ ↓H␈εα(9)␈αA␈αclean␈αpicture␈αis␈αboth␈αopen␈αand␈αclosed.
␈βπ1␈↓ ↓H␈εαB.␈ε∂␈α
The␈α
edge-tracing␈α
phase␈εα␈αis␈α
going␈α
to␈αpro␈α␈vide␈α
a␈α
description␈α
of␈αa␈α
clean␈α
picture␈α
that
␈βπ\␈↓ ↓H␈εαgro␈α␈ws␈αlinearly␈α(instead␈αof␈αquadratically)␈αwith␈αthe␈αresolution␈αof␈αthe␈αraster.
␈βλλ␈↓ α␈εαLet␈↓ αL␈ελP␈↓ αo␈εαbe␈α
a␈α
clean␈α	picture.␈αWe␈α
call␈α
the␈α
black␈α	pix␈α␈el␈↓ λ↓␈ελx␈↓ λ≡␈εαa␈ε∂␈α	boundary␈α
poin␈α␈t␈εα␈α
of␈↓ 
[␈ελP␈↓ 
␈␈εαif␈α	at
␈βλ3␈↓ ↓H␈εαleast␈αone␈αof␈↓ β¬␈ελx␈↓ β_␈εα's␈αfour␈αneigh␈α␈bors␈α(abo␈α␈v␈α␈e,␈αbelo␈α␈w,␈αleft,␈αor␈αrigh␈α␈t)␈αis␈αwhite.␈αThe␈αproblem
␈βλ↑␈↓ ↓H␈εαin␈αthis␈αphase␈αis␈αto␈αgroup␈αthe␈αboundary␈αpoin␈α␈ts␈αin␈α␈to␈α\closed␈αcy␈α␈cles␈αof␈αking␈αmo␈α␈v␈α␈es."
␈β		␈↓ ↓H␈εαIn␈αother␈α
w␈α␈ords,␈α
if␈α
there␈α
are␈↓ ¬↓␈ελm␈↓ ¬.␈εαboundary␈α
poin␈α␈ts,␈α
w␈α␈e␈αwan␈α␈t␈α
to␈α
arrange␈α
them␈αin␈α␈to␈↓ ,␈ελp
␈β	5␈↓ ↓H␈εαsequences
␈β	Q␈↓ ¬B␈ελx␈↓ ¬o␈εα,␈↓ ¬␈␈ελx␈↓ ε,␈εα,␈↓ ε<␈εα.␈αε.␈αε.␈↓ εl␈εα,␈↓ ε|␈ελx
␈β	←␈↓ ¬R␈ε¬1␈α↓1␈↓ ε⊂␈ε¬12␈↓ π
␈ε¬1␈↓ π≠␈εm
␈β	g␈↓ π5␈επ1
␈β	w␈↓ ¬B␈εα.
␈β
ε␈↓ ¬B␈εα.
␈β
∀␈↓ ¬B␈εα.
␈β
?␈↓ ¬B␈ελx␈↓ ¬p␈εα,␈↓ ε␈ελx␈↓ ε.␈εα,␈↓ ε>␈εα.␈αε.␈αε.␈↓ εn␈εα,␈↓ ε}␈ελx
␈β
M␈↓ ¬R␈εp␈↓ ¬a␈ε¬1␈↓ ε⊂␈εp␈↓ ε ␈ε¬2␈↓ π∂␈εp␈↓ π≡␈εm
␈β
U␈↓ π7␈ε
p
␈β∧␈↓ ↓H␈εαsuch␈α
that␈↓ αe␈ελm␈↓ β_␈εα+␈↓ βC␈ε⊗↓␈αε↓␈αε↓␈↓ βs␈εα+␈↓ ∧≥␈ελm␈↓ ∧U␈εα=␈↓ ¬β␈ελm␈↓ ¬-␈εαand␈αeach␈↓ εC␈ελx␈↓ π5␈εαis␈αa␈α
king␈αmo␈α␈v␈α␈e␈αaway␈αfrom␈↓ 
Q␈ελx␈↓ 
m␈εα;␈αalso
␈β⊃␈↓ β∧␈ε¬1␈↓ ∧<␈εp␈↓ 
b␈εi
␈β∩␈↓ εS␈εi␈↓ ε←␈ε¬(␈↓ εh␈εj␈↓ εv␈ε¬+␈α␈1␈α↓)
␈β/␈↓ ↓H␈ελx␈↓ α␈εαis␈α∞a␈α∂king␈α∞mo␈α␈v␈α␈e␈α∞away␈α∞from␈↓ ¬1␈ελx␈↓ ¬q␈εα.␈α∩A␈α∂king␈α∞mo␈α␈v␈α␈e␈α∞is␈α∞a␈α∞mo␈α␈v␈α␈e␈α∞one␈α∂step␈α∞up,␈α∞do␈α␈wn,
␈β<␈↓ ↓X␈εi␈↓ ↓d␈ε¬1␈↓ ¬B␈εi␈↓ ¬M␈εm
␈βE␈↓ ¬g␈ε
i
␈βZ␈↓ ↓H␈εαleft,␈αrigh␈α␈t,␈αor␈αdiagonally.␈αIn␈αthe␈αexample␈αabo␈α␈v␈α␈e,␈αall␈αelev␈α␈en␈αof␈αthe␈αboundary␈αpoin␈α␈ts
␈β¬␈↓ ↓H␈εαbelong␈αto␈αa␈αsingle␈αcy␈α␈cle
␈β"␈↓ ε
␈ε⊗∂␈↓ ε+␈ε⊗∂␈↓ εI␈ε⊗∂␈↓ εg␈ε⊗∂
␈β=␈↓ ε
␈ε⊗∂␈↓ εg␈ε⊗∂
␈βX␈↓ ε
␈ε⊗∂␈↓ εg␈ε⊗∂
␈βr␈↓ ε
␈ε⊗∂␈↓ ε+␈ε⊗∂␈↓ εI␈ε⊗∂
␈β
9␈↓ ↓H␈εαof␈αking␈α
mo␈α␈v␈α␈es,␈α
but␈αin␈α
general␈α
w␈α␈e␈αwill␈α
hav␈α␈e␈α
sev␈α␈eral␈αcy␈α␈cles␈α
if␈α
there␈αare␈α
sev␈α␈eral␈αdis-
␈β
d␈↓ ↓H␈εαconnected␈αareas␈αof␈αblack,␈αor␈αif␈αthere␈αare␈α\holes."
␈β∞⊂␈↓ α␈εαThe␈α
cy␈α␈cles␈α
of␈α
king␈α
mo␈α␈v␈α␈es␈α
can␈α
be␈α
still␈α
further␈α
re|ned,␈α
since␈α
it␈α
turns␈α
out␈αthat
␈β∞;␈↓ ↓H␈εαa␈α∂clean␈α⊂picture␈α∂has␈α∂cy␈α␈cles␈α⊂with␈α∂the␈α⊂follo␈α␈wing␈α∂property:␈α∪After␈α⊂a␈α∂diagonal␈α∂mo␈α␈v␈α␈e,
␈β∞↑␈↓ λs␈ε_¬
␈β∞f␈↓ ↓H␈εαthe␈α∂path␈α∂either␈α∞stays␈α∂in␈α∂the␈α∂same␈α∂direction␈α∂or␈α∂branches␈α∂4␈↓ λe␈εα5␈↓ 	∩␈εαto␈α∂the␈α∂left␈α∂or␈α∞righ␈α␈t
␈β∂.␈↓ ε:␈εα3
␈β⊃∂

␈β↓R␈↓ ↓H␈εαof␈α∂its␈α∞curren␈α␈t␈α∂direction.␈α∃After␈α∂a␈α∂rectilinear␈α∞mo␈α␈v␈α␈e,␈α⊂the␈α∂path␈α∂either␈α∂stays␈α∞mo␈α␈ving
␈β↓u␈↓ ε~␈ε_¬␈↓ π	␈ε_¬
␈β↓⎇␈↓ ↓H␈εαin␈α⊂the␈α⊂same␈α⊂direction␈α∂or␈α⊂branches␈α⊂4␈↓ ε␈εα5␈↓ ε9␈εαor␈α⊂9␈↓ ε{␈εα0␈↓ π)␈εαto␈α⊂the␈α⊂left␈α⊂or␈α⊂righ␈α␈t␈α⊂of␈α∂its␈α⊂curren␈α␈t
␈βα(␈↓ ↓H␈εαdirection.␈α∪Th␈α␈us␈α∞w␈α␈e␈α∂can␈α∞encode␈α∂each␈α∞cy␈α␈cle␈α∞as␈α∂a␈α∞compact␈α∂sequence␈α∞of␈α∞instruction
␈βαS␈↓ ↓H␈εαpairs␈α
\(n␈α␈um␈α␈ber,␈α
turn)",␈α∞meaning␈α
to␈α∞con␈α␈tin␈α␈ue␈α
in␈α
the␈α
same␈α∞direction␈α
for␈α
the␈α
giv␈α␈en
␈βα}␈↓ ↓H␈εαn␈α␈um␈α␈ber␈αof␈αsteps␈αand␈αthen␈αto␈αturn␈αin␈αthe␈αspeci|ed␈αway.␈αWhen␈αmo␈α␈ving␈αdiagonally,
␈ββ"␈↓ ε.␈ε_¬
␈ββ*␈↓ ↓H␈εαthe␈α
next␈α
turn␈α
will␈α
either␈α∞be␈↓ ¬	␈ελL␈↓ ¬.␈εαor␈ελ␈α
R␈εα␈α
(4␈↓ ε∨␈εα5␈↓ εJ␈εαleft␈α∞or␈α
righ␈α␈t);␈α∞otherwise␈α
it␈α
will␈α
be␈α
either
␈ββM␈↓ ∧x␈ε_¬␈↓ εα␈ε_¬␈↓ π␈ε_¬␈↓ λ,␈ε_¬
␈ββU␈↓ ↓H␈ελL␈↓ ↓`␈ελL␈↓ α¬␈εαor␈↓ α3␈ελL␈↓ αK␈ελR␈εα␈α∞or␈ελ␈α∞R␈↓ β9␈ελL␈↓ β↑␈εαor␈ελ␈α∞RR␈εα␈α∞(9␈↓ ∧j␈εα0␈↓ ¬∃␈εαleft,␈α∞4␈↓ ¬s␈εα5␈↓ ε∨␈εαleft,␈α∞4␈↓ ε⎇␈εα5␈↓ π(␈εαrigh␈α␈t,␈α∞9␈↓ λ≥␈εα0␈↓ λI␈εαrigh␈α␈t).␈α⊃We␈α∞may␈α
assume
␈β∧␈↓ ↓H␈εαthat␈αthe␈αpath␈αbegins␈αin␈αthe␈αupward␈αdirection␈αin␈αthe␈αleftmost␈αcolumn␈αof␈αthe␈αcy␈α␈cle;
␈β∧+␈↓ ↓H␈εαth␈α␈us,␈αthe␈αexample␈αboundary␈αabo␈α␈v␈α␈e␈αcan␈αbe␈αencoded␈αby␈αthe␈αsequence␈αof␈αking-mo␈α␈v␈α␈e
␈β∧V␈↓ ↓H␈εαinstructions
␈β¬α␈↓ βU␈εα(3,␈ελ␈αεRR␈εα),␈α*(3,␈ελ␈αεRR␈εα),␈α*(2,␈ελ␈αεR␈↓ ε\␈ελL␈↓ εt␈εα),␈α*(1,␈ελ␈αεR␈εα),␈α*(2,␈ελ␈αεRR␈εα).
␈β¬F␈↓ ↓H␈εα(The␈α∂|nal␈α⊂turn␈α⊂\␈ελRR␈εα"␈α⊂is␈α⊂redundan␈α␈t␈α∂and␈α⊂could␈α⊂be␈α⊂omitted.)␈α Together␈α⊂with␈α∂the
␈β¬q␈↓ ↓H␈εαcoordinates␈αof␈αthe␈αstarting␈αpoin␈α␈t,␈αthis␈αsequence␈αof␈αinstructions␈αcompletely␈αde|nes
␈βε≤␈↓ ↓H␈εαthe␈αcy␈α␈cle.
␈βεH␈↓ α␈εαYou␈αare␈αto␈αwrite␈αa␈αprogram␈αthat␈αproduces␈αsuch␈αinstruction␈αsequences␈αfor␈αthe
␈βεs␈↓ ↓H␈εαboundary␈α∞cy␈α␈cles␈α∂of␈α∞the␈α∂clean␈α∞72␈ε⊗␈α
α␈εα␈α	72␈α∂pictures␈α∞produced␈α∂by␈α∞y␈α␈our␈α∂|rst␈α∞program.
␈βπ≡␈↓ ↓H␈εαYou␈απshould␈αλalso␈αλpro␈α␈v␈α␈e␈απ(informally)␈αλthat␈αλy␈α␈our␈απprogram␈αλwill␈απhandle␈αλall␈αλclean␈απpictures.
␈β∂.␈↓ ε:␈εα4
␈β⊃∂

␈β↓R␈↓ λ↑␈εαCS204←Autumn␈α1978
␈βα∂␈↓ ↓H␈ε∩Problem␈α3.␈εα␈αCubic␈αspline␈αdrawing.␈↓ 	%(due␈αNo␈α␈v␈α␈em␈α␈ber␈α2)
␈βαS␈↓ ↓H␈εαThis␈α
problem␈α
arises␈α
in␈α
connection␈α
with␈α
drawing␈α
\nice"␈α
curv␈α␈es␈α	on␈α
a␈α
discrete␈α
raster.
␈ββε␈↓ ↓H␈εαWe␈αare␈αgiv␈α␈en␈αt␈α␈w␈α␈o␈αcubic␈αpolynomials
␈ββF␈↓ π'␈ε¬2␈↓ λ∃␈ε¬3
␈ββL␈↓ ∧X␈ελx␈↓ ∧k␈εα(␈↓ ∧w␈ελt␈↓ ¬∧␈εα)␈↓ ¬~␈εα=␈↓ ¬H␈ελx␈↓ ¬o␈εα+␈↓ ε≠␈ελx␈↓ ε:␈ελt␈↓ εO␈εα+␈↓ ε{␈ελx␈↓ π~␈ελt␈↓ π=␈εα+␈↓ πi␈ελx␈↓ λλ␈ελt␈↓ λ$␈εα,
␈ββZ␈↓ ¬X␈ε¬0␈↓ ε+␈ε¬1␈↓ π␈ε¬2␈↓ πz␈ε¬3
␈ββy␈↓ π(␈ε¬2␈↓ λ↔␈ε¬3
␈ββ␈␈↓ ∧W␈ελy␈↓ ∧k␈εα(␈↓ ∧w␈ελt␈↓ ¬∧␈εα)␈↓ ¬~␈εα=␈↓ ¬H␈ελy␈↓ ¬o␈εα+␈↓ ε≠␈ελy␈↓ ε;␈ελt␈↓ εP␈εα+␈↓ ε|␈ελy␈↓ π≠␈ελt␈↓ π?␈εα+␈↓ πk␈ελy␈↓ λ
␈ελt␈↓ λ%␈εα;
␈β∧␈↓ ¬Y␈ε¬0␈↓ ε,␈ε¬1␈↓ π
␈ε¬2␈↓ π|␈ε¬3
␈β∧'␈↓ ¬5␈ε↓␈␈↓ εD␈ε↓↓
␈β∧F␈↓ ↓H␈εαand␈α
w␈α␈e␈α∞wish␈α∞to␈α
plot␈α∞the␈α∞curv␈α␈e␈↓ ¬C␈ελx␈↓ ¬V␈εα(␈↓ ¬b␈ελt␈↓ ¬o␈εα),␈↓ ε␈ελy␈↓ ε∨␈εα(␈↓ ε+␈ελt␈↓ ε8␈εα)␈↓ ε`␈εαfor␈α∞0␈ε⊗␈α∀␈↓ πi␈ελt␈↓ λβ␈ε⊗∀␈εα␈α
1.␈α⊃But␈α
w␈α␈e␈α∞are␈α∞allo␈α␈w␈α␈ed␈α
to
␈β∧y␈↓ ↓H␈εαplot␈αonly␈αin␈α␈teger␈αpoin␈α␈ts,␈αmaking␈αking␈αmo␈α␈v␈α␈es.
␈β¬+␈↓ α␈εαHere␈α∂is␈α∞the␈α∂way␈α∞Kn␈α␈uth␈α∂solv␈α␈ed␈α∞this␈α∂problem␈α∂in␈α∞the␈α∂prototype␈α∞v␈α␈ersion␈α∂of␈α∞his
␈β¬]␈↓ ↓H␈εα\MET␈α⎇AF␈α␈ONT"␈απsystem␈απlast␈αλy␈α␈ear.␈α
First,␈αλhe␈αλmade␈απthe␈απproblem␈αλsligh␈α␈tly␈απmore␈απgeneral,
␈β¬p␈↓ ε␈ε↓␈␈↓ π≠␈ε↓↓
␈βε⊂␈↓ ↓H␈εαnamely␈αεto␈απplot␈απa␈απset␈απof␈αεcurv␈α␈e␈απsegmen␈α␈ts␈↓ ε~␈ελx␈↓ ε-␈εα(␈↓ ε9␈ελt␈↓ εF␈εα),␈↓ εb␈ελy␈↓ εv␈εα(␈↓ πα␈ελt␈↓ π∂␈εα)␈↓ π0␈εαfor␈↓ πc␈ελa␈↓ λ	␈ε⊗∀␈↓ λ7␈ελt␈↓ λN␈ε⊗∀␈↓ λ|␈ελb␈↓ 	≠␈εαand␈απfor␈απ1␈ε⊗␈α
∀␈↓ 
Y␈ελi␈↓ 
q␈ε⊗∀␈↓ ∨␈ελn␈↓ 4␈εα.
␈βε≥␈↓ πs␈εi␈↓ 		␈εi
␈βε?␈↓ εW␈ε¬1
␈βεB␈↓ ↓H␈εαFurthermore,␈α	it␈α	is␈αλpossible␈α	to␈αλassume␈α	that␈↓ εr␈εαhas␈αλbeen␈α	added␈α	to␈↓ 	∞␈ελx␈↓ 	6␈εαand␈αλto␈↓ 
!␈ελy␈↓ 
A␈εα,␈α	so␈αλthat
␈βεP␈↓ 	∨␈ε¬0␈↓ 
2␈ε¬0
␈βεS␈↓ εW␈∧εSεWα∂
␈βεU␈↓ ¬∧␈ε↓␈␈↓ ε∪␈ε↓↓␈↓ εU␈ε↓␈␈↓ εW␈ε¬2␈↓ λ≤␈ε↓↓
␈βεu␈↓ ↓H␈εαthe␈α∞closest␈α∞in␈α␈teger␈α∂poin␈α␈t␈α∞to␈↓ ¬∩␈ελx␈↓ ¬$␈εα(␈↓ ¬0␈ελt␈↓ ¬=␈εα),␈↓ ¬Y␈ελy␈↓ ¬n␈εα(␈↓ ¬z␈ελt␈↓ επ␈εα)␈↓ ε/␈εαis␈↓ εc␈ε⊗b␈↓ εq␈ελx␈↓ π∧␈εα(␈↓ π⊂␈ελt␈↓ π≥␈εα)␈ε⊗c␈εα,␈ε⊗␈αεb␈↓ πU␈ελy␈↓ πi␈εα(␈↓ πu␈ελt␈↓ λα␈εα)␈ε⊗c␈↓ λ*␈εα.␈α∀Under␈α∞these␈α∞conditions,
␈βπ'␈↓ ↓H␈εαthe␈αalgorithm␈α
repeatedly␈αdoes␈α
this:␈α
Terminate␈α
if␈↓ πQ␈ελn␈↓ πq␈εα=␈α0.␈α∞Otherwise,␈α
if␈↓ 
!␈ελx␈↓ 
4␈εα(␈↓ 
@␈ελt␈↓ 
M␈εα)␈α
is␈αnot
␈βπT␈↓ 
K␈ε→0
␈βπY␈↓ ↓H␈εαmonotonic␈α
bet␈α␈w␈α␈een␈↓ ∧¬␈ελt␈↓ ∧∨␈εα=␈↓ ∧O␈ελa␈↓ ¬␈εαand␈↓ ¬G␈ελt␈↓ ¬a␈εα=␈↓ ε∩␈ελb␈↓ ε1␈εα,␈α∞|nd␈α∞the␈α
roots␈α∞of␈α
its␈α∞derivativ␈α␈e␈↓ 
8␈ελx␈↓ 
R␈εα(␈↓ 
↑␈ελt␈↓ 
k␈εα)␈α
and
␈βπg␈↓ ∧`␈εn␈↓ ε∨␈εn
␈βλ␈↓ ↓H␈εαbreak␈αλthe␈α	in␈α␈terval␈α	in␈α␈to␈α	t␈α␈w␈α␈o␈αλor␈α	three␈α	in␈α␈tervals␈α	in␈α	which␈↓ λλ␈ελx␈↓ λ≠␈εα(␈↓ λ'␈ελt␈↓ λ4␈εα)␈α	is␈α	monotonic␈αλ(increasing
␈βλ>␈↓ ↓H␈ελn␈↓ ↓j␈εαaccordingly).␈α∂Similarly,␈α
the␈α
in␈α␈tervals␈α
are␈α
brok␈α␈en␈α
up␈α
ev␈α␈en␈αfurther,␈α∞if␈αnecessary,
␈βλq␈↓ ↓H␈εαso␈α∂that␈α⊂both␈↓ β ␈ελx␈↓ β3␈εα(␈↓ β?␈ελt␈↓ βL␈εα)␈α⊂and␈↓ ∧1␈ελy␈↓ ∧E␈εα(␈↓ ∧Q␈ελt␈↓ ∧↑␈εα)␈α⊂are␈α⊂monotonic␈α∂bet␈α␈w␈α␈een␈↓ π{␈ελt␈↓ λ_␈εα=␈↓ λL␈ελa␈↓ λ}␈εαand␈↓ 	G␈ελt␈↓ 	d␈εα=␈↓ 
_␈ελb␈↓ 
7␈εα.␈α↔If␈α∂no␈α␈w
␈βλ}␈↓ λ\␈εn␈↓ 
%␈εn
␈β	#␈↓ ↓H␈ε⊗b␈↓ ↓V␈ελx␈↓ ↓h␈εα(␈↓ ↓t␈ελa␈↓ α↔␈εα)␈ε⊗c␈εα␈α
=␈ε⊗␈α
b␈↓ αw␈ελx␈↓ β
␈εα(␈↓ β⊗␈ελb␈↓ β5␈εα)␈ε⊗c␈εα␈α
or␈ε⊗␈αb␈↓ ∧∩␈ελy␈↓ ∧&␈εα(␈↓ ∧2␈ελa␈↓ ∧T␈εα)␈ε⊗c␈εα␈α
=␈ε⊗␈α
b␈↓ ¬4␈ελy␈↓ ¬I␈εα(␈↓ ¬U␈ελb␈↓ ¬t␈εα)␈ε⊗c␈εα,␈α
draw␈αthe␈α
appropriate␈αhorizon␈α␈tal␈α
or␈α
v␈α␈ertical
␈β	0␈↓ α¬␈εn␈↓ β#␈εn␈↓ ∧C␈εn␈↓ ¬b␈εn
␈β	U␈↓ ↓H␈εαstraigh␈α␈t␈α
line␈α
(a␈α∞rook␈α
mo␈α␈v␈α␈e);␈α∞decrease␈↓ ε_␈ελn␈↓ ε;␈εαby␈α
1.␈α⊂Otherwise␈α
if␈ε⊗␈α∞b␈↓ λy␈ελx␈↓ 	␈εα(␈↓ 	_␈ελa␈↓ 	:␈εα)␈ε⊗c␈εα␈α
=␈ε⊗␈αb␈↓ 
∨␈ελx␈↓ 
2␈εα(␈↓ 
>␈ελb␈↓ 
]␈εα)␈ε⊗c␈α	ε␈εα␈αλ1
␈β	c␈↓ 	(␈εn␈↓ 
K␈εn
␈β
λ␈↓ ↓H␈εαand␈ε⊗␈αb␈↓ α≤␈ελy␈↓ α0␈εα(␈↓ α<␈ελa␈↓ α↑␈εα)␈ε⊗c␈εα␈α=␈ε⊗␈α
b␈↓ β?␈ελy␈↓ βS␈εα(␈↓ β←␈ελb␈↓ β}␈εα)␈ε⊗c␈αλε␈εα␈αλ1,␈αmak␈α␈e␈αthe␈αappropriate␈αdiagonal␈αking␈αmo␈α␈v␈α␈e;␈αdecrease␈↓ )␈ελn
␈β
∃␈↓ αM␈εn␈↓ βl␈εn
␈β
7␈↓ 	M␈ε¬1
␈β
:␈↓ ↓H␈εαby␈α1.␈α
Otherwise␈α
replace␈αthe␈α
in␈α␈terval␈α[␈↓ ε_␈ελa␈↓ ε;␈εα,␈↓ εK␈ελb␈↓ εj␈εα]␈αby␈α
t␈α␈w␈α␈o␈αin␈α␈tervals␈α
[␈↓ 	↔␈ελa␈↓ 	9␈εα,␈↓ 	`␈εα(␈↓ 	l␈ελa␈↓ 
↔␈εα+␈↓ 
C␈ελb␈↓ 
b␈εα)]␈αand
␈β
H␈↓ ε)␈εn␈↓ εX␈εn␈↓ 	'␈εn␈↓ 	⎇␈εn␈↓ 
P␈εn
␈β
K␈↓ 	M␈∧
K	Mα∂
␈β
M␈↓ 	M␈ε¬2
␈β
i␈↓ ↓V␈ε¬1
␈β
m␈↓ ↓H␈εα[␈↓ ↓h␈εα(␈↓ ↓t␈ελa␈↓ α∨␈εα+␈↓ αK␈ελb␈↓ αj␈εα),␈↓ βε␈ελb␈↓ β%␈εα];␈αincrease␈↓ ∧M␈ελn␈↓ ∧n␈εαby␈α1.
␈β
z␈↓ α¬␈εn␈↓ αX␈εn␈↓ β∪␈εn
␈β
⎇␈↓ ↓V␈∧
⎇↓Vα∂
␈β
␈␈↓ ↓V␈ε¬2
␈β∨␈↓ α␈εαKn␈α␈uth's␈α∂\binary␈α∞splitting"␈α∂method␈α∂seems␈α∂somewhat␈α∞elegan␈α␈t␈α∂at␈α∂|rst␈α∞glance,
␈βQ␈↓ ↓H␈εαbut␈α
the␈α
curv␈α␈es␈α∞it␈α
draws␈α
are␈α∞sometimes␈α
too␈α
skinn␈α␈y-looking␈α∞and␈α
they␈α
occasionally
␈β∧␈↓ ↓H␈εαcon␈α␈tain␈αundesirable␈αglitches␈αnear␈αpoin␈α␈ts␈αwhere␈↓ π&␈ελt␈↓ π>␈εαis␈αa␈αsimple␈αbinary␈αfraction.␈αEv␈α␈en
␈β6␈↓ ↓H␈εαwhen␈↓ α$␈ελx␈↓ α7␈εα(␈↓ αC␈ελt␈↓ αP␈εα)␈α
and␈↓ β+␈ελy␈↓ β?␈εα(␈↓ βK␈ελt␈↓ βX␈εα)␈αare␈α
linear,␈αthe␈α
results␈αare␈α
often␈αv␈α␈ery␈α
strange.␈αSo␈α
the␈αpurpose␈α
of
␈βi␈↓ ↓H␈εαthis␈α
problem␈α∞is␈α∞to␈α
help␈α∞Kn␈α␈uth␈α∞design␈α
a␈α∞better␈α∞routine␈α
for␈α∞the␈α∞real␈α
MET␈α⎇AF␈α␈ONT
␈β
≠␈↓ ↓H␈εαsystem.␈αThe␈αnew␈αapproach␈αis␈αin␈α␈tended␈αto␈αbe␈αfaster␈αand␈αto␈αgiv␈α␈e␈αbetter␈αcurv␈α␈es.
␈β
M␈↓ α␈εαHere's␈αthe␈αgerm␈αof␈αan␈αidea␈αthat␈αshould␈αw␈α␈ork␈αbetter:␈αBy␈αre|ning␈αthe␈αin␈α␈tervals
␈β∞␈↓ ↓H␈εαa␈α∂little␈α∂more,␈α⊂w␈α␈e␈α∂can␈α∂ensure␈α∂that␈↓ ¬k␈ελx␈↓ ¬}␈εα(␈↓ ε
␈ελt␈↓ ε↔␈εα)␈α∂and␈↓ ε{␈ελy␈↓ π∂␈εα(␈↓ π≠␈ελt␈↓ π(␈εα)␈α∂are␈α∂not␈α∂only␈α∂monotonic␈α∂in␈α∂each
␈β∞-␈↓ ∧⊗␈ε→0␈↓ ∧g␈ε→0
␈β∞2␈↓ ↓H␈εαin␈α␈terval,␈α
their␈αslope␈↓ ∧α␈ελy␈↓ ∧≥␈εα(␈↓ ∧)␈ελt␈↓ ∧6␈εα)/␈↓ ∧T␈ελx␈↓ ∧n␈εα(␈↓ ∧z␈ελt␈↓ ¬π␈εα)␈αis␈α
nev␈α␈er␈α
equal␈α
to␈ε⊗␈αε␈εα1␈α
(unless␈α
the␈αslope␈α
is␈α
constan␈α␈t␈α
in
␈β∞e␈↓ ↓H␈εαthe␈αin␈α␈terval).␈αThis␈αmeans␈αthat␈αthe␈αcurv␈α␈es␈αin␈αeach␈αin␈α␈terval␈αwill␈αno␈α␈w␈αbe␈αcon|ned␈αto
␈β∂.␈↓ ε:␈εα5
␈β⊃∂

␈β↓P␈↓ ↓H␈εαone␈αof␈αeigh␈α␈t␈α
\octan␈α␈ts";␈αby␈αrotation␈αand/or␈αre⎇ection␈α
w␈α␈e␈αcan␈αassume,␈αfor␈α
example,
␈βαα␈↓ ↓H␈εαthat␈↓ α∀␈ελx␈↓ α'␈εα(␈↓ α3␈ελt␈↓ α@␈εα)␈αand␈↓ β≤␈ελy␈↓ β0␈εα(␈↓ β<␈ελt␈↓ βI␈εα)␈αare␈αincreasing␈α
and␈αthat␈↓ εS␈ελy␈↓ εg␈εα(␈↓ εs␈ελt␈↓ π␈εα)␈αincreases␈αless␈αrapidly␈α
than␈↓ 
:␈ελx␈↓ 
M␈εα(␈↓ 
Y␈ελt␈↓ 
f␈εα).␈α⊗(In
␈βα0␈↓ βz␈ε→0␈↓ ∧t␈ε→0
␈βα5␈↓ ↓H␈εαother␈α
w␈α␈ords,␈α
0␈ε⊗␈α∀␈↓ βf␈ελy␈↓ ∧↓␈εα(␈↓ ∧
␈ελt␈↓ ∧~␈εα)␈ε⊗␈α∀␈↓ ∧b␈ελx␈↓ ∧|␈εα(␈↓ ¬λ␈ελt␈↓ ¬∃␈εα).)␈α≠No␈α␈w␈α
each␈α
mo␈α␈v␈α␈e␈α
is␈α
either␈α
one␈αrectilinear␈α
step␈α
to
␈βαg␈↓ ↓H␈εαthe␈αrigh␈α␈t,␈αor␈αone␈αdiagonal␈αstep␈αup␈αand␈αrigh␈α␈t.
␈βαz␈↓ 	∃␈ε↓␈␈↓ 
$␈ε↓↓
␈ββ→␈↓ α␈εαFind␈α∞an␈α∞e}cien␈α␈t␈α∂way␈α∞to␈α∞plot␈α∞a␈α∂giv␈α␈en␈α∞cubic␈α∞spline␈α∞curv␈α␈e␈↓ 	#␈ελx␈↓ 	6␈εα(␈↓ 	B␈ελt␈↓ 	O␈εα),␈↓ 	k␈ελy␈↓ 	␈␈εα(␈↓ 
␈ελt␈↓ 
_␈εα)␈↓ 
A␈εαfor␈α∞0␈ε⊗␈α
∀
␈ββG␈↓ ¬∀␈ε→0␈↓ ε∪␈ε→0
␈ββL␈↓ ↓H␈ελt␈↓ ↓c␈ε⊗∀␈εα␈α∞1,␈α∞assuming␈α∂that␈α∞0␈ε⊗␈α∞∀␈↓ ¬␈ελy␈↓ ¬≠␈εα(␈↓ ¬'␈ελt␈↓ ¬4␈εα)␈ε⊗␈α∞∀␈↓ ε␈ελx␈↓ ε~␈εα(␈↓ ε&␈ελt␈↓ ε3␈εα)␈α∂for␈α∞0␈ε⊗␈α∞∀␈↓ πZ␈ελt␈↓ πu␈ε⊗∀␈εα␈α∞1.␈α∪Your␈α∞algorithm␈α∞should
␈ββ}␈↓ ↓H␈εαdecide␈αλas␈α	rapidly␈α	as␈αλpossible␈α	whether␈α	or␈αλnot␈α	each␈αλsuccessiv␈α␈e␈α	righ␈α␈t␈α␈ward␈α	mo␈α␈v␈α␈e␈αλshould
␈β∧1␈↓ ↓H␈εαhav␈α␈e␈αslope␈α
0␈αor␈α1.␈α∞Then␈αincorporate␈α
y␈α␈our␈αmethod␈α
in␈α␈to␈αan␈α
e}cien␈α␈t␈αsubroutine␈αfor
␈β∧C␈↓ 	$␈ε↓␈␈↓ 
=␈ε↓↓
␈β∧c␈↓ ↓H␈εαthe␈α
general␈α
problem.␈α≠[␈ε∂Hin␈α␈t:␈εα␈α∂We␈α
w␈α␈ould␈α
lik␈α␈e␈α∞to␈α
plot␈α
the␈α
poin␈α␈ts␈↓ 	2␈ελn␈↓ 	H␈εα,␈ε⊗␈αεb␈↓ 	f␈ελy␈↓ 	z␈εα(␈↓ 
ε␈ελt␈↓ 
#␈εα)␈ε⊗c␈↓ 
K␈εα,␈α
where
␈β∧p␈↓ 
⊃␈εn
␈β¬∃␈↓ ↓H␈ελx␈↓ ↓Z␈εα(␈↓ ↓f␈ελt␈↓ αβ␈εα)␈α
=␈↓ αG␈ελn␈↓ α]␈εα;␈α	but␈αλit␈αλis␈απprobably␈αλnot␈αλnecessary␈αλto␈αλkno␈α␈w␈αλthe␈απvalue␈αλof␈↓ 	↔␈ελt␈↓ 	<␈εαv␈α␈ery␈απaccurately.]
␈β¬#␈↓ ↓q␈εn␈↓ 	"␈εn
␈β∂.␈↓ ε:␈εα6
␈β⊃∂

␈β↓R␈↓ λ↑␈εαCS204←Autumn␈α1978
␈βαλ␈↓ ↓H␈ε∩Problem␈α4.␈εα␈αA␈αlanguage␈αfor␈αGosper␈αarithmetic.␈↓ 	∪(due␈αNo␈α␈v␈α␈em␈α␈ber␈α16)
␈βαE␈↓ ↓H␈εαThe␈αmain␈α
purpose␈αof␈αthis␈αproblem␈αis␈αnot␈αto␈αdesign␈αa␈αcomputer␈α
program←instead,
␈βαp␈↓ ↓H␈εαw␈α␈e␈απwill␈απtry␈απto␈απdesign␈απa␈απgood␈ε∂␈αλprogramming␈απlanguage␈εα␈απof␈απa␈απnew␈απtype␈απ(related␈απsomewhat
␈ββ≠␈↓ ↓H␈εαto␈α⊂the␈α∂so-called␈α⊂\data-⎇o␈α␈w"␈α⊂languages␈α⊂being␈α⊂discussed␈α⊂no␈α␈wadays␈α⊂in␈α∂connection
␈ββF␈↓ ↓H␈εαwith␈α∞database␈α∂systems).␈α∪The␈α∂seman␈α␈tics␈α∞of␈α∂a␈α∞certain␈α∞new␈α∂computational␈α∞scheme
␈ββr␈↓ ↓H␈εαwill␈αbe␈α
sk␈α␈etched␈α
belo␈α␈w;␈α
y␈α␈our␈α
task␈α
will␈α
be␈α
to␈αsuggest␈α
a␈α
good␈α
in␈α␈terface␈α
by␈α
which␈αa
␈β∧≥␈↓ ↓H␈εαuser␈αwill␈αbe␈αable␈αto␈αuse␈αthe␈αscheme␈αin␈α␈telligen␈α␈tly.
␈β∧H␈↓ α␈εαHere's␈α
the␈α∞sk␈α␈etch:␈α∞Ev␈α␈ery␈α∞real␈α
n␈α␈um␈α␈ber␈↓ εi␈ελx␈↓ π	␈εαcan␈α∞be␈α
represen␈α␈ted␈α
in␈α∞a␈α
unique␈α
way
␈β∧s␈↓ ↓H␈εαas␈αa␈αcon␈α␈tin␈α␈ued␈αfraction
␈β¬⊂␈↓ εd␈εα1
␈β¬'␈↓ ¬*␈ελx␈↓ ¬Q␈εα+
␈β¬4␈↓ ¬:␈ε¬0
␈β¬7␈↓ ε↓␈∧¬7ε↓α↓X
␈β¬D␈↓ π
␈εα1
␈β¬[␈↓ ε↓␈ελx␈↓ ε(␈εα+
␈β¬i␈↓ ε⊃␈ε¬1
␈β¬l␈↓ εX␈∧¬lεXα⎇
␈β¬t␈↓ εX␈ελx␈↓ ε}␈εα+␈↓ π*␈ε⊗↓␈αε↓␈αε↓
␈βε↓␈↓ εh␈ε¬2
␈βε(␈↓ ↓H␈εαwhere␈↓ α+␈ελx␈↓ αR␈εαis␈απan␈αλin␈α␈teger␈απand␈↓ ∧S␈ελx␈↓ ∧r␈εα,␈↓ ¬∧␈ελx␈↓ ¬#␈εα,␈↓ ¬5␈εα.␈αε.␈αε.␈↓ ¬g␈εαare␈απin|nitely␈αλman␈α␈y␈απpositiv␈α␈e␈αλin␈α␈tegers;␈α	or␈απperhaps
␈βε6␈↓ α<␈ε¬0␈↓ ∧c␈ε¬1␈↓ ¬∃␈ε¬2
␈βεS␈↓ ↓H␈ελx␈↓ ↓q␈εα=␈ε⊗␈α
1␈εα␈α
for␈α
some␈↓ β[␈ελk␈↓ βm␈εα,␈αin␈α
which␈α
case␈↓ ¬Z␈ελx␈↓ ε%␈εα,␈↓ ε9␈ελx␈↓ πβ␈εα,␈↓ π_␈εα.␈αε.␈αε.␈↓ πL␈εαdo␈α
not␈αexist.␈αFor␈α
con␈α␈v␈α␈enience␈α
in
␈βεa␈↓ ↓X␈εk␈↓ ¬k␈εk␈↓ ¬y␈ε¬+1␈↓ εJ␈εk␈↓ εX␈ε¬+2
␈βε␈␈↓ ↓H␈εαnotation,␈απw␈α␈e␈απwrite␈↓ βd␈ελx␈↓ ∧↓␈εα=␈↓ ∧/␈ελx␈↓ ∧O␈εα+␈ε⊗␈α↓?␈↓ ¬ε␈ελx␈↓ ¬%␈εα,␈↓ ¬5␈ελx␈↓ ¬T␈εα,␈↓ ¬d␈εα.␈αε.␈αε.␈↓ ε∀␈ε⊗?␈εα.␈α
The␈↓ ε␈␈ελx␈↓ π≡␈εα's␈απare␈απcalled␈αε\partial␈απquotien␈α␈ts"␈απof␈↓ "␈ελx␈↓ 4␈εα.
␈βπ␈↓ ∧?␈ε¬0␈↓ ¬⊗␈ε¬1␈↓ ¬E␈ε¬2␈↓ π∂␈εk
␈βπ*␈↓ α␈εαR.␈αW.␈α
Gosper␈αhas␈αdev␈α␈eloped␈α
a␈αset␈αof␈α
routines␈αthat␈αdo␈α
arithmetic␈αdirectly␈αon
␈βπU␈↓ ↓H␈εαthe␈α⊂con␈α␈tin␈α␈ued␈α⊂fraction␈α⊂represen␈α␈tations␈α⊃of␈α⊂n␈α␈um␈α␈bers.␈α→His␈α⊂routines␈α⊂hav␈α␈e␈α⊂the␈α⊂neat
␈βλ␈↓ ↓H␈εαproperty␈αthat,␈αwhen␈αcomputing␈αsomething␈αlik␈α␈e
␈βλ%␈↓ ¬.␈ε↓␈␈↓ πA␈ε↓↓␈↓ λβ␈ε↓␈␈↓ 
↔␈ε↓↓
␈βλD␈↓ αW␈ελz␈↓ αy␈εα+␈ε⊗␈αλ?␈↓ β7␈ελz␈↓ βR␈εα,␈↓ βb␈ελz␈↓ β|␈εα,␈↓ ∧␈εα.␈αε.␈αε.␈↓ ∧<␈ε⊗?␈α≡ ␈↓ ¬<␈ελx␈↓ ¬c␈εα+␈ε⊗␈αλ?␈↓ ε!␈ελx␈↓ ε@␈εα,␈↓ εP␈ελx␈↓ εo␈εα,␈↓ ε␈␈εα.␈αε.␈αε.␈↓ π/␈ε⊗?␈↓ πW␈εα+␈↓ λ⊃␈ελy␈↓ λ8␈εα+␈ε⊗␈αλ?␈↓ λv␈ελy␈↓ 	⊗␈εα,␈↓ 	&␈ελy␈↓ 	E␈εα,␈↓ 	U␈εα.␈αε.␈αε.␈↓ 
¬␈ε⊗?␈↓ 
%␈εα,
␈βλR␈↓ αc␈ε¬0␈↓ βC␈ε¬1␈↓ βn␈ε¬2␈↓ ¬M␈ε¬0␈↓ ε2␈ε¬1␈↓ εa␈ε¬2␈↓ λ"␈ε¬0␈↓ 	π␈ε¬1␈↓ 	7␈ε¬2
␈β	λ␈↓ ↓H␈εαthey␈αlook␈α
at␈αjust␈α
enough␈αof␈α
the␈↓ ¬C␈ελx␈↓ ¬l␈εαand␈↓ ε3␈ελy␈↓ ε]␈εαto␈α
determine␈↓ λ2␈ελz␈↓ λZ␈εαbefore␈↓ 	F␈ελz␈↓ 	m␈εαis␈α
output,␈αfor
␈β	∃␈↓ ¬T␈εi␈↓ εD␈εj␈↓ λ>␈εk␈↓ 	R␈εk
␈β	3␈↓ ↓H␈ελk␈↓ ↓c␈εα=␈α
0,␈α
1,␈α
2,␈↓ ββ␈εα.␈αε.␈αε.␈↓ β9␈εα.␈αTh␈α␈us␈α	it␈α
is␈α	best␈α
to␈α	think␈α
of␈α	his␈α
arithmetic␈α	procedures␈α
as␈ε∂␈α	coroutines
␈β	↑␈↓ ↓H␈εαthat␈α∂produce␈α∂one␈α∂partial␈α⊂quotien␈α␈t␈α∂at␈α∂a␈α⊂time␈α∂when␈α∂called␈α∂on.␈α⊗Gosper's␈α∂addition
␈β

␈↓ ↓H␈εαcoroutine␈α
for␈↓ β!␈ελz␈↓ β=␈ε⊗ ␈↓ βn␈ελx␈↓ ∧
␈εα+␈↓ ∧7␈ελy␈↓ ∧Y␈εαis␈α
e{ectiv␈α␈ely␈α∞hook␈α␈ed␈α∞up␈α
to␈α∞the␈α∞coroutine␈α∞for␈↓ 
$␈ελx␈↓ 
E␈εαand␈α
the
␈β
5␈↓ ↓H␈εαcoroutine␈α	for␈↓ β_␈ελy␈↓ β,␈εα;␈α
when␈α	the␈↓ ∧V␈ελz␈↓ ∧n␈εαcoroutine␈α	is␈α	ask␈α␈ed␈α	for␈α	a␈α	new␈α	partial␈α	quotien␈α␈t,␈α	it␈α	will␈α	call
␈β
`␈↓ ↓H␈εαon␈α	the␈↓ α2␈ελx␈↓ αN␈εαand/or␈↓ βD␈ελy␈↓ βa␈εαcoroutines␈α	for␈α
more␈α	information,␈α
but␈α	only␈α
as␈α	m␈α␈uch␈α	as␈α	necessary.
␈β␈↓ α␈εαActually␈ε∂␈αev␈α␈ery␈εα␈αn␈α␈umeric␈αquan␈α␈tity␈αin␈αthe␈αsystem␈αis␈αa␈αcoroutine,␈αat␈αleast␈αat␈αthe
␈β6␈↓ ↓H␈εαuser's␈αlev␈α␈el␈α
of␈α
abstraction,␈αand␈α
these␈α
coroutines␈αare␈α
connected␈α
together␈αin␈α
a␈αpos-
␈βb␈↓ ↓H␈εαsibly␈α	gigan␈α␈tic␈α
net␈α␈w␈α␈ork.␈αThere␈α	are␈α
no␈α
ordinary␈α
n␈α␈um␈α␈bers,␈α
in␈α
the␈α
old-fashioned␈α	static
␈β
␈↓ ↓H␈εαsense␈αof␈αsome␈α
bit␈αrepresen␈α␈tation␈αstored␈αsomewhere;␈αn␈α␈umeric␈αquan␈α␈tities␈α
are␈αtotally
␈β8␈↓ ↓H␈εαdynamic.␈α
Nothing␈α
is␈αev␈α␈er␈α
computed␈α\to␈α
the␈α
end,"␈αthe␈α
calculations␈αjust␈α
get␈αmore
␈βc␈↓ ↓H␈εαand␈αmore␈αprecise␈αif␈αthis␈αis␈αcalled␈αfor.
␈β
∞␈↓ α␈εαWhen␈α
started␈α
or␈α
restarted,␈α
a␈α
coroutine␈α
for␈↓ π7␈ελx␈↓ πW␈εαwill␈α
sooner␈α
or␈α
later␈α
produce␈α
an
␈β
:␈↓ ↓H␈εαoutput␈α∂that␈α∂is␈α∂either␈α∂the␈α∂next␈α∂partial␈α∂quotien␈α␈t␈α∂for␈↓ πz␈ελx␈↓ λ≠␈εαor␈α∂it␈α∂will␈α∂produce␈α∂a␈α∂coded
␈β
e␈↓ ↓H␈εαmessage␈αthat␈αmeans␈α\␈↓ ∧≥␈ελx␈↓ ∧;␈εαis␈αindeterminate,␈αbut␈αits␈αnext␈αpartial␈αquotien␈α␈t␈αis␈αan␈α␈ything
␈β∞⊂␈↓ ↓H␈εαbet␈α␈w␈α␈een␈↓ αU␈ελa␈↓ αu␈εαand␈↓ β>␈ελb␈↓ β\␈εαinclusiv␈α␈e,␈α∂and␈α∂don't␈α∂ask␈α∂me␈α∂for␈α∂an␈α␈y␈α∂more␈α∂information."␈α≡This
␈β∞;␈↓ ↓H␈εαallo␈α␈ws␈α
us␈α
to␈α
deal␈α
with␈α
inaccurate␈α
input␈α
data,␈α
producing␈α
exactly␈α
as␈α
m␈α␈uch␈α
output
␈β∞f␈↓ ↓H␈εαprecision␈αas␈αis␈αlegitimate.
␈β∂.␈↓ ε:␈εα7
␈β⊃∂

␈β↓R␈↓ ↓H␈εαAssume␈αthat␈αthe␈αfollo␈α␈wing␈αtypes␈αof␈αcoroutines␈αare␈αavailable:
␈βαλ␈↓ α␈εα(1)␈α∂Giv␈α␈en␈α∂t␈α␈w␈α␈o␈α∂decimal␈α∞n␈α␈um␈α␈bers␈↓ ε⊃␈ελx␈↓ ε3␈εαand␈↓ ε|␈ελ∂␈↓ π
␈εα,␈α∂output␈α∂the␈α∂partial␈α∂quotien␈α␈ts␈α∂for␈α∞a
␈βα3␈↓ α␈εαn␈α␈um␈α␈ber␈αthat␈αis␈αindeterminate␈αbut␈αbet␈α␈w␈α␈een␈↓ π2␈ελx␈↓ πM␈ε⊗␈␈↓ πy␈ελ∂␈↓ λ∪␈εαand␈↓ λY␈ελx␈↓ λt␈εα+␈↓ 	 ␈ελ∂␈↓ 	.␈εα.
␈βα↑␈↓ α␈εα(2)␈αGiv␈α␈en␈αt␈α␈w␈α␈o␈αcoroutines␈↓ ¬≠␈ελx␈↓ ¬:␈εαand␈↓ ε␈ελy␈↓ ε∀␈εα,␈αoutput␈αthe␈αpartial␈αquotien␈α␈ts␈αfor␈↓ 
%␈ελx␈↓ 
@␈εα+␈↓ 
l␈ελy␈↓ ␈εα.
␈ββ	␈↓ α␈εα(3)␈αGiv␈α␈en␈αt␈α␈w␈α␈o␈αcoroutines␈↓ ¬≠␈ελx␈↓ ¬:␈εαand␈↓ ε␈ελy␈↓ ε∀␈εα,␈αoutput␈αthe␈αpartial␈αquotien␈α␈ts␈αfor␈↓ 
%␈ελx␈↓ 
@␈ε⊗␈␈↓ 
l␈ελy␈↓ ␈εα.
␈ββ4␈↓ α␈εα(4)␈αGiv␈α␈en␈αt␈α␈w␈α␈o␈αcoroutines␈↓ ¬≠␈ελx␈↓ ¬:␈εαand␈↓ ε␈ελy␈↓ ε∀␈εα,␈αoutput␈αthe␈αpartial␈αquotien␈α␈ts␈αfor␈↓ 
%␈ελx␈↓ 
@␈ε⊗α␈↓ 
l␈ελy␈↓ ␈εα.
␈ββ`␈↓ α␈εα(5)␈αGiv␈α␈en␈αt␈α␈w␈α␈o␈αcoroutines␈↓ ¬≠␈ελx␈↓ ¬:␈εαand␈↓ ε␈ελy␈↓ ε∀␈εα,␈αoutput␈αthe␈αpartial␈αquotien␈α␈ts␈αfor␈↓ 
%␈ελx␈↓ 
8␈εα/␈↓ 
J␈ελy␈↓ 
↑␈εα.
␈β∧␈↓ α␈εα(6)␈αGiv␈α␈en␈αa␈αcoroutine␈↓ ∧g␈ελx␈↓ ∧z␈εα,␈αoutput␈αthe␈αdecimal␈αdigits␈αof␈↓ λT␈ελx␈↓ λg␈εα.
␈β∧A␈↓ ↓H␈εαEach␈αλof␈α	these␈α	coroutines␈αλwill␈α	produce␈α	its␈αλoutputs␈α	one␈α	at␈αλa␈α	time,␈α	as␈α	called␈α	for.␈α
There
␈β∧l␈↓ ↓H␈εαis␈αλalso␈α	a␈α	procedure␈αλthat,␈α
giv␈α␈en␈αλcoroutines␈↓ εD␈ελx␈↓ ε←␈εαand␈↓ π"␈ελy␈↓ π6␈εα,␈α	will␈α	produce␈α	one␈αλof␈α	four␈αλoutputs:
␈β¬↔␈↓ ↓H␈εα\␈↓ ↓Z␈ελx␈↓ ↓v␈εα<␈↓ α$␈ελy␈↓ α9␈εα",␈α\␈↓ αs␈ελx␈↓ β∂␈εα=␈↓ β=␈ελy␈↓ βQ␈εα",␈α\␈↓ ∧␈ελx␈↓ ∧(␈εα>␈↓ ∧V␈ελy␈↓ ∧j␈εα",␈αor␈α\indeterminate".
␈β¬B␈↓ α␈εαAll␈α
this␈α
sounds␈α
v␈α␈ery␈α
nice,␈αbut␈α
there␈α
is␈α
a␈α
serious␈α
problem␈α
that␈α
has␈α
been␈α
glossed
␈β¬n␈↓ ↓H␈εαo␈α␈v␈α␈er:␈α∩In␈α⊂order␈α∂to␈α∂produce␈α∂results␈α⊂in␈α∂|nite␈α∂time,␈α⊃the␈α∂coroutines␈α∂sometimes␈α∂hav␈α␈e
␈βε→␈↓ ↓H␈εαto␈αmak␈α␈e␈αguesses␈α
and␈αretract␈αbad␈αguesses␈α
later.␈α
Furthermore␈αthe␈αcomparison␈αpro-
␈βεD␈↓ ↓H␈εαcedure␈α
migh␈α␈t␈α
hav␈α␈e␈α∞to␈α
giv␈α␈e␈α
a␈α
|fth␈α∞output,␈α
\I␈α∞can't␈α
|gure␈α
it␈α∞out␈α
ev␈α␈en␈α
though␈α
I'v␈α␈e
␈βεo␈↓ ↓H␈εαcheck␈α␈ed␈α
lots␈αof␈α
partial␈α
quotien␈α␈ts␈α
of␈↓ ¬{␈ελx␈↓ ε~␈εαand␈↓ εa␈ελy␈↓ εu␈εα."␈α≠The␈α
reason␈α
can␈α
be␈α
understood␈αby
␈βπ~␈↓ ↓H␈εαconsidering␈αthe␈αanalogous␈αsituation␈αwhere␈αw␈α␈e␈αare␈αw␈α␈orking␈αin␈αthe␈αdecimal␈αn␈α␈um␈α␈ber
␈βπF␈↓ ↓H␈εαsystem␈αinstead␈α
of␈α
with␈α
con␈α␈tin␈α␈ued␈α
fractions:␈α
After␈α
reading␈α
|nitely␈α
man␈α␈y␈α
digits␈αof
␈βπk␈↓ ↓l␈∧πk↓lα∩
␈βπl␈↓ ↓H␈ε⊗p
␈βπq␈↓ ↓l␈εα2␈↓ α	␈εα=␈α1.4142␈↓ β"␈εα.␈αε.␈αε.␈↓ βR␈εα,␈α
w␈α␈e␈α
will␈α
not␈α
be␈αable␈α
to␈α
tell␈α
if␈α
the␈αsquare␈α
of␈α
this␈α
quan␈α␈tity␈α
is␈αless
␈βλ≤␈↓ ↓H␈εαthan␈α∞2␈α∞or␈α∞not,␈α∂ev␈α␈en␈α∞though␈α∞w␈α␈e␈α∞kno␈α␈w␈α∞that␈α∞it␈α∞is␈α∞at␈α∞least␈α∞1.99999999999␈↓ 
*␈εα.␈αε.␈αε.␈↓ 
h␈εα(say);
␈βλG␈↓ ↓H␈εαw␈α␈e␈αhav␈α␈e␈αto␈αwait␈αforev␈α␈er␈αbefore␈αw␈α␈e␈αkno␈α␈w␈αev␈α␈en␈αthe␈α|rst␈αdigit␈αof␈αthe␈αproduct.␈αWhen
␈βλr␈↓ ↓H␈εαGosper's␈α∂routines␈α⊂appear␈α⊂to␈α⊂be␈α∂computing␈α⊂too␈α⊂long,␈α⊂he␈α⊂mak␈α␈es␈α⊂them␈α⊂produce␈α∂a
␈β	≡␈↓ ↓H␈εαguessed-at␈α∞result;␈α∂if␈α
this␈α∞turns␈α∞out␈α∞to␈α∞be␈α∞wrong,␈α∂they␈α∞will␈α∞later␈α∞output␈α
a␈α∞partial
␈β	I␈↓ ↓H␈εαquotien␈α␈t␈α
that␈α
is␈α∞zero␈α
or␈α
negativ␈α␈e,␈α∞in␈α
such␈α∞a␈α
way␈α
that␈α
the␈α∞con␈α␈tin␈α␈ued␈α
fraction␈α
will
␈β	t␈↓ ↓H␈εαstill␈αevaluate␈αto␈αthe␈αcorrect␈α|nal␈αvalue.
␈β
∨␈↓ α␈εαSo␈αthat's␈αthe␈αgeneral␈αidea.␈αOur␈αgoal␈αis␈αto␈αdesign␈αa␈αsuitable␈αuser␈αprogramming
␈β
J␈↓ ↓H␈εαlanguage.␈αTo␈α
mak␈α␈e␈α
the␈α	problem␈α
more␈α
explicit,␈α
y␈α␈ou␈α
are␈α
ask␈α␈ed␈α
to␈α
illustrate␈α
ho␈α␈w␈α	y␈α␈ou
␈β
v␈↓ ↓H␈εαw␈α␈ould␈αsolv␈α␈e␈αthe␈αfollo␈α␈wing␈αt␈α␈w␈α␈o␈αproblems␈αusing␈αthe␈αlanguage␈αy␈α␈ou␈αdesign:
␈β,␈↓ α␈εα(a)␈αCalculate␈αa␈αroot␈αof␈αan␈α␈y␈αgiv␈α␈en␈αcubic␈αequation.
␈βW␈↓ α␈εα(b)␈αλSolv␈α␈e␈αλa␈απsystem␈αλof␈↓ ∧N␈ελn␈↓ ∧k␈εαsim␈α␈ultaneous␈αλlinear␈αλequations␈αλ(by␈αλsome␈απstraigh␈α␈tforward
␈βα␈↓ α␈εαscheme).
␈β8␈↓ ↓H␈εαFor␈α∞each␈α∂of␈α∞these␈α∂tasks,␈α∂presen␈α␈t␈α∂a␈α∞sample␈α∂program␈α∞in␈α∂y␈α␈our␈α∞new␈α∂language.␈α∪Also
␈βc␈↓ ↓H␈εαgiv␈α␈e␈α
a␈α
brief␈α
description␈α
of␈α
the␈α
features␈α
of␈α
y␈α␈our␈α
language.␈α~(But␈α
don't␈α
attempt␈α
to
␈β
∞␈↓ ↓H␈εαimplemen␈α␈t␈αa␈αcompiler␈αfor␈αit,␈αwait␈αun␈α␈til␈αy␈α␈ou␈αtak␈α␈e␈αCS240␈αor␈αsomething.)
␈β∂.␈↓ ε:␈εα8
␈β⊃∂

␈β↓R␈↓ λ↑␈εαCS204←Autumn␈α1978
␈βαλ␈↓ ↓H␈ε∩Problem␈α5.␈εα␈αKriegspiel␈αendgame.␈↓ 	)(due␈αDecem␈α␈ber␈α5)
␈βαE␈↓ α␈εαIn␈α∂this␈α⊂problem␈α∂w␈α␈e␈α∂are␈α∂concerned␈α∂with␈α⊂the␈α∂game␈α∂of␈α∂chess␈α⊂where␈α∂there␈α∂is␈α∂a
␈βαp␈↓ ↓H␈εαwhite␈α
king␈α
and␈αwhite␈α
rook␈αagainst␈α
a␈αblack␈α
king.␈αAn␈αeasy␈α
checkmate,␈αy␈α␈ou␈α
say;␈αbut
␈ββ≠␈↓ ↓H␈εαthere's␈αa␈αt␈α␈wist:␈αThe␈αwhite␈αplay␈α␈er␈αdoes␈αnot␈αkno␈α␈w␈αwhere␈αthe␈αblack␈αking␈αis.
␈ββF␈↓ α␈εαThe␈αgame␈αstarts␈αwith␈αthe␈αwhite␈αking␈αand␈αrook␈αat␈αtheir␈αnormal␈αopening␈αposi-
␈ββr␈↓ ↓H␈εαtions,␈α
while␈α
the␈α
black␈α
king␈α
may␈α
be␈α
an␈α␈ywhere␈α
else␈α(but␈α
not␈α
in␈α
check);␈α
White␈α
mo␈α␈v␈α␈es
␈β∧≥␈↓ ↓H␈εα|rst.␈α
Whenev␈α␈er␈αλWhite␈αλmak␈α␈es␈αλa␈αλmo␈α␈v␈α␈e,␈α	he␈αλor␈αλshe␈αλreceiv␈α␈es␈αλone␈αλof␈αλthe␈απfollo␈α␈wing␈αλreplies:
␈β∧S␈↓ ↓b␈εαa)␈↓ α␈εαCheckmate,␈αy␈α␈ou␈αwin.
␈β∧}␈↓ ↓`␈εαb)␈↓ α␈εαStalemate,␈αit's␈αa␈αdraw.
␈β¬)␈↓ ↓d␈εαc)␈↓ α␈εαThat␈α	mo␈α␈v␈α␈e␈αλof␈α	y␈α␈ours␈α	is␈αλillegal␈α	because␈αλit␈α	puts␈α	y␈α␈our␈αλking␈α	next␈αλto␈α	mine;␈α
try␈αλagain.
␈β¬T␈↓ ↓`␈εαd)␈↓ α␈εαYour␈α∞mo␈α␈v␈α␈e␈α∞put␈α∞me␈α∞in␈α∞check,␈α∂but␈α
it␈α∞was␈α∞not␈α∞checkmate␈α∞so␈α∞I␈α∞hav␈α␈e␈α∞made␈α∞m␈α␈y
␈βε␈↓ α␈εαnext␈αmo␈α␈v␈α␈e.
␈βε+␈↓ ↓d␈εαe)␈↓ α␈εαYour␈αmo␈α␈v␈α␈e␈αdid␈αnot␈αput␈αme␈αin␈αcheck,␈αand␈αI␈αhav␈α␈e␈αmade␈αm␈α␈y␈αnext␈αmo␈α␈v␈α␈e.
␈βεa␈↓ ↓H␈εαIt␈αλis␈α	possible␈α	for␈α	White␈α	to␈αλforce␈α	checkmate␈α	in␈α	|nitely␈α	man␈α␈y␈αλmo␈α␈v␈α␈es,␈α
but␈α	the␈αλwinning
␈βπ␈↓ ↓H␈εαstrategy␈αis␈αnot␈αeasy␈αto␈αdisco␈α␈v␈α␈er,␈αso␈αa␈αgood␈αBlack␈αwill␈αusually␈αbe␈αable␈αto␈αescape.
␈βπ7␈↓ α␈εαYour␈α
problem␈αis␈α
to␈α
design␈αand␈α
program␈αa␈α
Black␈α
strategy␈αthat␈α
plays␈α\in␈α␈telli-
␈βπb␈↓ ↓H␈εαgen␈α␈tly";␈αin␈αparticular,␈αy␈α␈our␈αprogram␈αshould␈αbe␈αable␈αto␈αsurviv␈α␈e␈αat␈αleast␈α100␈αmo␈α␈v␈α␈es
␈βλ∞␈↓ ↓H␈εαagainst␈α∩t␈α␈w␈α␈o␈α∩di{eren␈α␈t␈α∩White␈α∩programs␈α∩supplied␈α∪by␈α∩the␈α∩grader.␈α$(These␈α∩White
␈βλ9␈↓ ↓H␈εαprograms␈α	will,␈α	of␈α	course,␈α
be␈α	incorrect␈α	attacking␈α	strategies,␈α	typical␈α	of␈α	what␈α	a␈α	play␈α␈er
␈βλd␈↓ ↓H␈εαmigh␈α␈t␈αtry␈α
if␈αhe␈αdoesn't␈α
kno␈α␈w␈αthe␈α
secret␈αof␈α
winning.)␈α~You␈αwill␈α
not␈αbe␈α
able␈αto␈αsee
␈β	∂␈↓ ↓H␈εαthe␈αgrader's␈α
second␈α
program␈αun␈α␈til␈α
the␈α
|nal␈αcon␈α␈test␈α
actually␈αtak␈α␈es␈α
place␈α
(nor␈αwill
␈β	:␈↓ ↓H␈εαhe␈αlook␈α
at␈α
y␈α␈our␈αprogram);␈α
but␈α
the␈α
grader's␈α|rst␈α
program␈α
will␈αbe␈α
available␈α
to␈αaid
␈β	f␈↓ ↓H␈εαy␈α␈ou␈αin␈αpreliminary␈αtesting.
␈β
⊃␈↓ α␈εαThis␈αgame␈αis␈αdi{eren␈α␈t␈αfrom␈αtrue␈αKriegspiel␈αin␈αthat␈αBlack␈αdoes␈αkno␈α␈w␈α
the␈αposi-
␈β
<␈↓ ↓H␈εαtions␈α∞of␈α∂White's␈α∂pieces.␈α∀Furthermore,␈α⊂Black␈α∂does␈α∞not␈α∂hav␈α␈e␈α∂to␈α∂be␈α∂committed␈α∞to
␈β
g␈↓ ↓H␈εαparticular␈α
king␈αmo␈α␈v␈α␈es␈α
at␈α
each␈α
step,␈α
he␈α
or␈α
she␈α
is␈α
allo␈α␈w␈α␈ed␈α
to␈α
imagine␈α
being␈α
in␈αan␈α␈y
␈β∩␈↓ ↓H␈εαset␈α
of␈α∞possible␈α
positions␈α∞consisten␈α␈t␈α
with␈α∞what␈α∞White␈α
has␈α∞been␈α
told.␈α⊃After␈α
seeing
␈β>␈↓ ↓H␈εαwhat␈α	White␈α	does,␈α	Black␈α	has␈α	the␈α	righ␈α␈t␈α	to␈α	decide␈α	what␈α	the␈α	past␈α	history␈αλactually␈α	was.
␈β∂.␈↓ ε:␈εα9
␈β⊃∂/FONT#1=cmathx[XGP,SYS]=↓↓/FONT#2=cmr10[XGP,SYS]=∂≤"'()+,-./0123456789:;<=>ABCDEFGHIKLMNOPRSTUWY[\]←abcdefghijklmnopqrstuvwxyz{|⎇}}/FONT#5=cmr7[XGP,SYS]=()+01233/FONT#7=cmr5[XGP,SYS]=11/FONT#8=cmi10[XGP,SYS]=∂≡LPRabikmnptwxyzz/FONT#11=cmi7[XGP,SYS]=COijkmnpp/FONT#13=cmi5[XGP,SYS]=ipp/FONT#15=cms10[XGP,SYS]=-:HTabcdeghilmnoprstuvyy/FONT#18=cmb10[XGP,SYS]=.12345Pbelmorr/FONT#22=cmsy10[XGP,SYS]=↓αε∂∀≡∨ 123?bcfgjpp/FONT#24=cmsy8[XGP,SYS]=¬¬/FONT#25=cmsy7[XGP,SYS]=≡∨00